package com.huawei.M01.iterator.F23;

import java.util.HashMap;
import java.util.Map;

/**
 * 动态规划
 *
 * @author 11
 */
public class StoneGame2 {
    public int stoneGameII(int[] piles) {
        // 先求前缀和
        int[] preSumPiles = new int[piles.length + 1];
        for (int i = 0; i < piles.length; i++) {
            preSumPiles[i + 1] = piles[i] + preSumPiles[i];
        }
        // 使用记忆搜索法
        Map<Integer, Integer> cache = new HashMap<>();

        return (preSumPiles[piles.length] + dp(cache, piles, preSumPiles, 0, 1)) / 2;
    }

    private int dp(Map<Integer, Integer> cache, int[] piles, int[] preSumPiles, int i, int m) {

        if (i == piles.length) {
            return 0;
        }

        int key = i * 201 + m;
        if (!cache.containsKey(key)) {
            int maxValue = Integer.MIN_VALUE;
            for (int x = 1; x <= 2 * m; x++) {
                // 超出长度，直接返回
                if (i + x > piles.length) {
                    break;
                }

                maxValue = Math.max(maxValue, preSumPiles[i + x] - preSumPiles[i] - dp(cache, piles, preSumPiles, i + x, Math.max(m, x)));
            }
            cache.put(key, maxValue);
        }
        return cache.get(key);
    }
}
